﻿/*------------------------------------------------------------------------

SLIST.HPP v1.0.1

Copyright 楊志賢 CxxlMan, 2014
All Rights Reserved

** 主要在提供 cxxlList 沒法做到的任意節點的提取和增刪
** 可用 template 參數 isUnique 決定同一個物件可不可以重複放入
** 不提供巡行功能，但可利用 cxxlList_Create() 取得 cxxlList 物件再用它做巡行

------------------------------------------------------------------------*/

#if !defined(__SLIST_HPP_CxxlMan)
#define __SLIST_HPP_CxxlMan

#include <CXXLAVLTREE.HPP>

namespace CxxlMan
{

template <typename T, bool isUnique>
class SList:virtual public cxxlObject
{
  struct Node:public cxxlObject
  {
    Smart_Ptr<T> Obj_Ptr;
    Node *prev,*next;

    // Constructor
    Node(T *S,SList<T,isUnique> *Host)
      :CxxlMan::cxxlObject(CxxlMan::Spirit_Easy),
       Obj_Ptr(S,Host)
    {
    }
  };


  // 存放 Node 節點，Key 為物件的指標，以方便快速尋找
  class Search_Tree:public CxxlMan::cxxlAVL_Tree<Node, T*, isUnique>
  {
    bool cxxlFASTCALL isLeftAt(T *O_Key,T *addKey) const
    {
      return O_Key < addKey;
    }

    bool cxxlFASTCALL isEqual(T *O_Key, T *findKey)  const
    {
      return O_Key == findKey;
    }

  public:
    // Constructor
    Search_Tree()
      :CxxlMan::cxxlObject(CxxlMan::Spirit_Urgent), 
      CxxlMan::cxxlAVL_Tree< SList::Node, T*, isUnique >(CxxlMan::Spirit_Urgent) // 其實 Spirit_Urgent 不會用到，因實例 m_Search_Tree 是成員變數，沒放入 Smart_Ptr
    {
    }

  }m_Search_Tree;

  CriticalSec csObject;

  unsigned long count;
  Node *head,*tail;

  // Clone() 時用來產生延伸類別的物件
  // 所以延伸別必須覆載
  virtual SList<T,isUnique> * cxxlFASTCALL CreateSelf(ISpirit *spirit) const
  {
    return new SList<T,isUnique>(spirit);
  }


public:
  // Constructor
  SList(ISpirit *spirit = Spirit_Easy)
    :cxxlObject(spirit)
  {
    head = new Node(NULL,this);
    tail = new Node(NULL,this);

    head->next = tail;
    tail->prev = head;

  }

  // Destructor
  virtual ~SList() 
  {
    ClearAll();
    delete head;
    delete tail;
  }



  // 將物件放入最前位置
  // 失敗表示要放入的物件已放入過了
  inline bool cxxlFASTCALL Push_Front(const Smart_Ptr<T> &addObj_Ptr);

  // 將物件放入最後位置
  // 失敗表示要放入的物件已放入過了
  inline bool cxxlFASTCALL Push_Back(const Smart_Ptr<T> &addObj_Ptr);

  // 將物件放入 refObj_Ptr 之前
  // 失敗表示要放入的物件已放入過了，或是 refObj_Ptr 不存在
  inline bool cxxlFASTCALL Add_Prev(const Smart_Ptr<T> &addObj_Ptr, const Smart_Ptr<T> &refObj_Ptr);

  // 將物件放入 refObj_Ptr 之後
  // 失敗表示要放入的物件已放入過了，或是 refObj_Ptr 不存在
  inline bool cxxlFASTCALL Add_Next(const Smart_Ptr<T> &addObj_Ptr, const Smart_Ptr<T> &refObj_Ptr);



  // 刪除(放棄持有)所有物件
  inline void cxxlFASTCALL ClearAll();

  // 刪除(放棄持有)最前面一個物件
  inline void cxxlFASTCALL Delete_Front();

  // 刪除(放棄持有)最後一個物件
  inline void cxxlFASTCALL Delete_Back();

  // 刪除(放棄持有)指定的物件
  inline void cxxlFASTCALL Delete(const Smart_Ptr<T> &delObj_Arg);




  // 取得物件存放的個數
  inline unsigned long cxxlFASTCALL GetCount() const;

  // 取得最前一個物件
  inline Smart_Ptr<T> cxxlFASTCALL GetObj_Front() const;

  // 取得最後一個物件
  inline Smart_Ptr<T> cxxlFASTCALL GetObj_Back() const;

  // 取出最前一個物件並刪除(放棄持有)
  inline Smart_Ptr<T> cxxlFASTCALL Pop_Front();

  // 取出最後一個物件並刪除(放棄持有)
  inline Smart_Ptr<T> cxxlFASTCALL Pop_Back();

  // 取得位於 refObj_Ptr 的前一個物件
  inline Smart_Ptr<T> cxxlFASTCALL GetObj_Prev(const Smart_Ptr<T> &refObj_Ptr) const;

  // 取得位於 refObj_Ptr 的後一個物件
  inline Smart_Ptr<T> cxxlFASTCALL GetObj_Next(const Smart_Ptr<T> &refObj_Ptr) const;

  // 取回並移除位於 refObj_Ptr 的前一個物件
  inline Smart_Ptr<T> cxxlFASTCALL Pump_Prev(const Smart_Ptr<T> &refObj_Ptr);

  // 取回並移除位於 refObj_Ptr 的後一個物件
  inline Smart_Ptr<T> cxxlFASTCALL Pump_Next(const Smart_Ptr<T> &refObj_Ptr);



  // 將所有物件放入一個串列物件(cxxlList)後傳回
  inline Smart_Ptr<cxxlList<T> > cxxlFASTCALL cxxlList_Create() const;



  // 自我複製
  // 傳回相同內容的同類形容器物件
  inline Smart_Ptr<SList<T,isUnique> > cxxlFASTCALL Clone() const;

};


// 取回並移除位於 refObj_Ptr 的前一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::Pump_Prev(const Smart_Ptr<T> &refObj_Ptr)
{
  CriticalSecHandle AutoCSH(csObject);

  Smart_Ptr<T> r_Ptr = GetObj_Prev(refObj_Ptr);

  if(r_Ptr.isNULL() == false)
    this->Delete(r_Ptr);

  return r_Ptr;
}

// 取回並移除位於 refObj_Ptr 的後一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::Pump_Next(const Smart_Ptr<T> &refObj_Ptr)
{
  CriticalSecHandle AutoCSH(csObject);

  Smart_Ptr<T> r_Ptr = GetObj_Next(refObj_Ptr);

  if(r_Ptr.isNULL() == false)
    this->Delete(r_Ptr);

  return r_Ptr;
}


// 取得位於 refObj_Ptr 的前一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::GetObj_Prev(const Smart_Ptr<T> &refObj_Ptr) const
{
  CriticalSecHandle AutoCSH(csObject);

  Smart_Ptr<Node> refNode_Ptr = m_Search_Tree.GetObj(refObj_Ptr);

  if(refNode_Ptr.isNULL())
    return false;

  return refNode_Ptr->prev->Obj_Ptr;
}

// 取得位於 refObj_Ptr 的後一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::GetObj_Next(const Smart_Ptr<T> &refObj_Ptr) const
{
  CriticalSecHandle AutoCSH(csObject);

  Smart_Ptr<Node> refNode_Ptr = m_Search_Tree.GetObj(refObj_Ptr);

  if(refNode_Ptr.isNULL())
    return false;

  return refNode_Ptr->next->Obj_Ptr;
}


// 將所有物件放入一個串列物件(cxxlList)後傳回
template <typename T, bool isUnique>
Smart_Ptr<cxxlList<T> > cxxlFASTCALL SList<T,isUnique>::cxxlList_Create() const
{
  CriticalSecHandle AutoCSH(csObject);

  cxxlList<T> *cxxlList_Temp = new cxxlList<T>(this->GetSpirit());

  Node *pNode = head->next;

  while(pNode != tail)
  {
    cxxlList_Temp->Push_Back(pNode->Obj_Ptr);
    pNode = pNode->next;
  }

  return cxxlList_Temp;
}



// 將物件放入 refObj_Ptr 之前
// 失敗表示要放入的物件已放入過了，或是 refObj_Ptr 不存在
template <typename T, bool isUnique>
bool cxxlFASTCALL cxxlFASTCALL SList<T,isUnique>::Add_Prev(const Smart_Ptr<T> &addObj_Ptr, const Smart_Ptr<T> &refObj_Ptr)
{
  CriticalSecHandle AutoCSH(csObject);

  if(m_Search_Tree.GetObj(addObj_Ptr).isNULL() == false)
    return false;

  Smart_Ptr<Node> refNode_Ptr = m_Search_Tree.GetObj(refObj_Ptr);

  if(refNode_Ptr.isNULL())
    return false;

  Node *temp = new Node(addObj_Ptr,this);

  temp->next = (Node *)refNode_Ptr;
  temp->prev = refNode_Ptr->prev;

  refNode_Ptr->prev->next = temp;
  refNode_Ptr->prev = temp;
  
  m_Search_Tree.Add(temp, (T*)addObj_Ptr);

  return true;
}

// 將物件放入 refObj_Ptr 之後
// 失敗表示要放入的物件已放入過了，或是 refObj_Ptr 不存在
template <typename T, bool isUnique>
bool cxxlFASTCALL SList<T,isUnique>::Add_Next(const Smart_Ptr<T> &addObj_Ptr, const Smart_Ptr<T> &refObj_Ptr)
{
  CriticalSecHandle AutoCSH(csObject);

  if(m_Search_Tree.GetObj(addObj_Ptr).isNULL() == false)
    return false;

  Smart_Ptr<Node> refNode_Ptr = m_Search_Tree.GetObj(refObj_Ptr);

  if(refNode_Ptr.isNULL())
    return false;

  Node *temp = new Node(addObj_Ptr,this);

  temp->prev = (Node *)refNode_Ptr;
  temp->next = refNode_Ptr->next;

  refNode_Ptr->next->prev = temp;
  refNode_Ptr->next = temp;

  m_Search_Tree.Add(temp, (T*)addObj_Ptr);

  return true;
}


// 刪除(放棄持有)所有物件
template <typename T, bool isUnique>
void cxxlFASTCALL SList<T,isUnique>::ClearAll()
{
  csObject.Enter();

  m_Search_Tree.ClearAll();

  head->next = tail;
  tail->prev = head;

  csObject.Leave();
};

// 將物件放入最前位置
// 失敗表示要放入的物件已放入過了
template <typename T, bool isUnique>
bool cxxlFASTCALL SList<T,isUnique>::Push_Front(const Smart_Ptr<T> &S)
{
  CriticalSecHandle AutoCSH(csObject);

  if( m_Search_Tree.GetObj(S).isNULL() == false )
    return false;

  Node *temp = new Node(S,this);
  temp->next = head->next;
  temp->prev = head;
  head->next->prev = temp;
  head->next = temp;
  
  m_Search_Tree.Add(temp, (T*)S);

  return true;

}

// 將物件放入最後位置
// 失敗表示要放入的物件已放入過了
template <typename T, bool isUnique>
bool cxxlFASTCALL SList<T,isUnique>::Push_Back(const Smart_Ptr<T> &S)
{
  CriticalSecHandle AutoCSH(csObject);

  if(m_Search_Tree.GetObj(S).isNULL() == false)
    return false;

  Node *temp = new Node(S,this);
  temp->prev = tail->prev;
  temp->next = tail;
  tail->prev->next = temp;
  tail->prev = temp;

  m_Search_Tree.Add(temp, (T *)S);

  return true;
}


// 刪除(放棄持有)最前面一個物件
template <typename T, bool isUnique>
void cxxlFASTCALL SList<T,isUnique>::Delete_Front()
{
  csObject.Enter();
  Node *temp = head->next;
  if(temp != tail)
  {
    head->next = temp->next;    
    temp->next->prev = head;

    m_Search_Tree.Delete((T *)temp->Obj_Ptr);
  }
  csObject.Leave();
}

// 刪除(放棄持有)最後一個物件
template <typename T, bool isUnique>
void cxxlFASTCALL SList<T,isUnique>::Delete_Back()
{
  csObject.Enter();
  Node *temp = tail->prev;
  if(temp != head)
  {
    tail->prev = temp->prev;
    temp->prev->next = tail;

    m_Search_Tree.Delete((T *)temp->Obj_Ptr);
  }
  csObject.Leave();
}

// 取得物件存放的個數
template <typename T, bool isUnique>
unsigned long cxxlFASTCALL SList<T,isUnique>::GetCount() const
{
  return m_Search_Tree.GetCount();
}

// 取得最前一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::GetObj_Front() const
{
  CriticalSecHandle AutoCSH(csObject);
  if(head->next != tail)
    return head->next->Obj_Ptr;
  else
    return Smart_Ptr<T>(NULL);
}

// 取得最後一個物件
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::GetObj_Back() const
{
  CriticalSecHandle AutoCSH(csObject);
  if(tail->prev != head)
    return tail->prev->Obj_Ptr;
  else
    return Smart_Ptr<T>(NULL);
}

// 取出最前一個物件並刪除(放棄持有)
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::Pop_Front()
{
  CriticalSecHandle AutoCSH(csObject);
  if(head->next != tail)
  {
    Smart_Ptr<T> temp = head->next->Obj_Ptr;
    Delete_Front();
    return temp;
  }
  else
    return Smart_Ptr<T>(NULL);
 }

// 取出最後一個物件並刪除(放棄持有)
template <typename T, bool isUnique>
Smart_Ptr<T> cxxlFASTCALL SList<T,isUnique>::Pop_Back()
{
  CriticalSecHandle AutoCSH(csObject);
  if(tail->prev != head)
  {
    Smart_Ptr<T> temp = tail->prev->Obj_Ptr;
    Delete_Back();
    return temp;
  }
  else
    return Smart_Ptr<T>(NULL);
}  


// 自我複製
// 傳回相同內容的同類形容器物件
template <typename T, bool isUnique>
Smart_Ptr<SList<T,isUnique> > cxxlFASTCALL SList<T,isUnique>::Clone() const
{
  CriticalSecHandle AutoCSH(csObject);

  SList<T,isUnique> *R = CreateSelf(GetSpirit());

  Node *temp = head->next;
  while(temp != tail)
  {
    R->Push_Back(temp->Obj_Ptr);
    temp = temp->next;
  }

  return Smart_Ptr<cxxlList<T> >(R);
}

// 刪除(放棄持有)指定的物件
template <typename T, bool isUnique>
void cxxlFASTCALL SList<T,isUnique>::Delete(const Smart_Ptr<T> &delObj_Arg)
{
  csObject.Enter();
  Smart_Ptr<Node> temp_Ptr = m_Search_Tree.Pump(delObj_Arg);
  if(temp_Ptr.isNULL() != true)
  {
    temp_Ptr->prev->next = temp_Ptr->next;
    temp_Ptr->next->prev = temp_Ptr->prev;
  }
  csObject.Leave();
}


}   /* namespace CxxlMan */
#endif

